package com.zhugang.week12;

import java.util.ArrayList;
import java.util.List;

/**
 * @program algorithms
 * @description: findContinuousSequence
 * @author: chanzhugang
 * @create: 2022/09/07 19:00
 */
public class FindContinuousSequence {

    /**
     * 剑指offer 57-II 和为s的连续正数序列
     *
     * @param target
     * @return
     */
    public int[][] findContinuousSequence(int target) {
        // 和为target的连续正整数序列(至少两个数)
        // 滑动窗口 ：左边界sum-、右边界sum+
        List<int[]> result = new ArrayList<>();
        int p = 1;
        int q = 2;
        int sum = 3;
        while (p < q) {
            if (sum == target) {
                int[] arr = new int[q - p + 1];
                for (int i = p; i <= q; i++) {
                    arr[i - p] = i;
                }
                result.add(arr);

                sum = sum - p;
                p++;

                q++;
                sum = sum + q;
            } else if (sum < target) {
                // 右边界滑动
                q++;
                sum = sum + q;
            } else {
                // 左边界滑动
                sum = sum - p;
                p++;
            }
        }
        int[][] array = new int[result.size()][];
        for (int i = 0; i < result.size(); i++) {
            array[i] = result.get(i);
        }
        return array;
    }
}